<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    // 从第一个点开始寻找附近最近的点连接，，然后在被连接的点再次寻找距离最短的点，
    let arr = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
    var minCostConnectPoints = function (points, fir = 0) {
      let minCost = undefined
      let minIndex = undefined
      let haslist = new Array(points.length)
      haslist[0] = true
      // for (let i = 1; i < points.length; i++) {
      //   add+=ddd(minCost,minIndex,haslist,points)
      // }
      console.log('add', ddd(minCost, minIndex, haslist, points));
    };
    function ddd(minCost, minIndex, haslist, points, fir = 0, now = 1, add = 0) {
      for (let i = 0; i < points.length; i++) {
        if (!haslist[i]) {
          const pointsi = points[i]
          const pointsfir = points[fir]
          let Cost = (pointsi[0] - pointsfir[0]) ** 2 + (pointsi[1] - pointsfir[1]) ** 2
          // console.log('Cost',Cost);
          if (minCost != undefined) {
            minCost = Cost <= minCost ? Cost : minCost
            minIndex = i
          } else {
            minCost = Cost
            minIndex = i
          }
        }
      }
      haslist[minIndex] = true
      now += 1
      add += minCost
      console.log('add', add);
      if (now < points.length) {
        // minCost,minIndex,haslist,points,fir=0,now=1,add=0
        ddd(minCost, minIndex, haslist, points, 0, now, add)
      }
      return add
    }
    // minCostConnectPoints(arr)
  </script>
  <script>
    var minCostConnectPoints = function (points) {
      const dist = (x, y) => {
        return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1])
      }

      const n = points.length;
      const dsu = new DisjointSetUnion(n);
      const edges = [];

      for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
          // 得到每两个点之间的横纵坐标差值的和
          edges.push([dist(i, j), i, j]);
        }
      }
      console.log('edges', edges);
      // 将数组按两个点之间最小的距离排序
      edges.sort((a, b) => a[0] - b[0]);

      let ret = 0, num = 1;
      for (const [length, x, y] of edges) {
        if (dsu.unionSet(x, y)) {
          ret += length;
          num += 1;
          if (num === n) {
            break;
          }
        }
      }
      return ret;
    };

    class DisjointSetUnion {
      constructor(n) {
        this.n = n;//需要计算点数量
        // this.rank = new Array(n).fill(1);//使用初始值1填充所有需要连接的点
        this.f = new Array(n).fill(0).map((element, index) => index);
        console.log('f', this.f, this.rank);
      }

      find(x) {
        console.log('this.f[x] === x', this.f, this.f[x], x);
        if (this.f[x] === x) {
          return x;
        }
        this.f[x] = this.find(this.f[x]);
        return this.f[x];
      }
      unionSet(x, y) {
        // 此时的x是第一层循环的点，如果当前点和第二层循环的点是同一个点那么就是重复
        let fx = this.find(x), fy = this.find(y);
        console.log('fx', fx, 'fy', fy);
        if (fx === fy) {
          return false;
        }
        // if (this.rank[fx] < this.rank[fy]) {
        //   [fx, fy] = [fy, fx];
        // }
        // this.rank[fx] += this.rank[fy];
        //此时第二层循环的点y已经和第一层循环的点x连接了，就让第y个点等于x
        this.f[fy] = fx;
        return true;
      }
    }
    console.log('minCostConnectPoints(arr)', minCostConnectPoints(arr)); 
  </script>
  <script>
    let arr2 = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
    var minCostConnectPoints = function (points) {
      //将两个坐标之间的横纵坐标差值相加并依这个条件进行对比，取值之前没有连接的距离最近的两个点
      const distance=(x,y)=>{return Math.abs((points[x][1]-points[y][0])+(points[x][1]-points[y][0]))}
      const n=points.length
      let distArr=[]
      // 为什么是j=i+1
      for (let i = 0; i < n; i++) {
        for (let j = i+1; j < n; j++) {
          distArr.push([distance(i,j),i,j])
        }
      }
      console.log('distArr',distArr);
    }
    minCostConnectPoints(arr2)
  </script>
</body>

</html> 